// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-04-02 16:08
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetCodeT.TREE;

import org.junit.jupiter.api.Test;

/**
 * 线状树实现
 */
class NumArray {

    /**
     * 线状树节点
     */
    class Node {
        int start, end;
        Node left, right;
        int value;

        public Node(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }

    /**
     * 线段树根节点
     */
    Node root;

    public NumArray(int[] nums) {
        int n = nums.length;
        root = buildSegTree(nums, 0, n - 1);
    }

    public void update(int index, int val) {
        if (index < root.start || index > root.end) {
            return;
        }
        update(root, index, val);
    }

    public void update(Node root, int index, int val) {
        if (root.start == root.end) {
            root.value = val;
            return;
        }
        int mid = root.start + ((root.end - root.start) >> 1);
        if (mid >= index) {
            update(root.left, index, val);
        } else {
            update(root.right, index, val);
        }
        root.value = root.left.value + root.right.value;
    }

    public int sumRange(int left, int right) {
        if (left < 0 || left > right) {
            return 0;
        }
        return sumRange(root, left, right);
    }

    private int sumRange(Node root, int left, int right) {
        if (root.start == left && root.end == right) {
            return root.value;
        }
        int mid = root.start + ((root.end - root.start) >> 1);
        if (mid >= right) {
            return sumRange(root.left, left, right);
        } else if (mid < left) {
            return sumRange(root.right, left, right);
        }
        int leftValue = sumRange(root.left, left, mid);
        int rightValue = sumRange(root.right, mid + 1, right);
        return leftValue + rightValue;
    }

    /**
     * 线段树构建方法
     */
    public Node buildSegTree(int[] source, int left, int right) {
        Node root = new Node(left, right);
        if (left == right) {
            root.value = source[left];
            return root;
        }
        int mid = left + ((right - left) >> 1);
        root.left = buildSegTree(source, left, mid);
        root.right = buildSegTree(source, mid + 1, right);
        root.value = root.left.value + root.right.value;
        return root;
    }


    public static void main(String[] args) {
        NumArray na = new NumArray(new int[]{1, 3, 5});
        System.out.println(na.sumRange(0, 2));
        na.update(1, 2);
        System.out.println(na.sumRange(0, 2));
    }

}